package com.sheng.leetcode.year2023.month02.day22;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/02/22
 * <p>
 * 877. 石子游戏<p>
 * <p>
 * Alice 和 Bob 用几堆石子在做游戏。一共有偶数堆石子，排成一行；每堆都有 正 整数颗石子，数目为 piles[i] 。<p>
 * 游戏以谁手中的石子最多来决出胜负。石子的 总数 是 奇数 ，所以没有平局。<p>
 * Alice 和 Bob 轮流进行，Alice 先开始 。 每回合，玩家从行的 开始 或 结束 处取走整堆石头。<p>
 * 这种情况一直持续到没有更多的石子堆为止，此时手中 石子最多 的玩家 获胜 。<p>
 * 假设 Alice 和 Bob 都发挥出最佳水平，当 Alice 赢得比赛时返回 true ，当 Bob 赢得比赛时返回 false 。<p>
 * <p>
 * 示例 1：<p>
 * 输入：piles = [5,3,4,5]<p>
 * 输出：true<p>
 * 解释：<p>
 * Alice 先开始，只能拿前 5 颗或后 5 颗石子 。<p>
 * 假设他取了前 5 颗，这一行就变成了 [3,4,5] 。<p>
 * 如果 Bob 拿走前 3 颗，那么剩下的是 [4,5]，Alice 拿走后 5 颗赢得 10 分。<p>
 * 如果 Bob 拿走后 5 颗，那么剩下的是 [3,4]，Alice 拿走后 4 颗赢得 9 分。<p>
 * 这表明，取前 5 颗石子对 Alice 来说是一个胜利的举动，所以返回 true 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：piles = [3,7,2,3]<p>
 * 输出：true<p>
 * <p>
 * 提示：<p>
 * 2 <= piles.length <= 500<p>
 * piles.length 是 偶数<p>
 * 1 <= piles[i] <= 500<p>
 * sum(piles[i]) 是 奇数<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/stone-game">877. 石子游戏</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode0877 {

    @Test
    public void test01() {
        int[] piles = {5, 3, 4, 5};
//        int[] piles = {3, 7, 2, 3};
        System.out.println(new Solution877().stoneGame(piles));
    }
}

class Solution877 {
    public boolean stoneGame(int[] piles) {
        /**
         * 判断是否存在 A 先拿，并且一定能获胜的方法
         * 对于先手玩家有两种拿法
         * 拿开头的 piles[i]：先手玩家手里有了 piles[i]，那么后手玩家则只能选择在区间 i + 1 <-> j 这个区间进行选择，
         * 那么本次选择中，先手玩家比后手玩家多的最大石子个数，就是这差值
         * 即 dp[i][j] = piles[i] + (-dp[i + 1][j])
         * 拿结尾的 piles[j]：先手玩家手里有了 piles[j]，那么后手玩家则只能选择在区间 i <-> j - 1 这个区间进行选择，
         * 那么本次选择中，先手玩家比后手玩家多的最大石子个数，就是这差值
         * 即 dp[i][j] = piles[j] + (-dp[i][j - 1])
         * 在这两种情况中，选择差值更大的一种情况：dp[i][j] = Math.max(piles[i] + (-dp[i + 1][j]), piles[j] + (-dp[i][j - 1]));
         */
        int n = piles.length;
        if (n == 0) {
            return false;
        }
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = piles[i];
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = Math.max(piles[i] + (-dp[i + 1][j]), piles[j] + (-dp[i][j - 1]));
            }
        }
        return dp[0][n - 1] >= 0;

        /**
         * int n = ps.length;
         * int[][] f = new int[n + 2][n + 2];
         * for (int len = 1; len <= n; len++) { // 枚举区间长度
         *     for (int l = 1; l + len - 1 <= n; l++) { // 枚举左端点
         *         int r = l + len - 1; // 计算右端点
         *         int a = ps[l - 1] - f[l + 1][r];
         *         int b = ps[r - 1] - f[l][r - 1];
         *         f[l][r] = Math.max(a, b);
         *     }
         * }
         * return f[1][n] > 0;
         *
         *
         * 作者：AC_OIer
         * 链接：https://leetcode.cn/problems/stone-game/solution/gong-shui-san-xie-jing-dian-qu-jian-dp-j-wn31/
         * 来源：力扣（LeetCode）
         * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         */
    }
}
